#ifndef DTALINKEDLIST_H_INCLUDED
#define DTALINKEDLIST_H_INCLUDED


#include <iostream>
#include <vector>
using namespace std;


//------------------------------------------------------------------------------
/*
 * Lista ligada do tipo:
 * noh       noh    noh     noh
 * cabeca->  next-> next->  next-> NULL
 *           data   data    data
 *
 * A cabeca é o início da lista e nao contem dado algum. Isso torna o tratamento das operacoes de insercao, busca e remocao homogeneas
 * A classe permite que dados repetidos sejam inseridos. O controle para isso nao ocorrer, deve ser realizado em outras classes, bastando que
 * o dado seja buscado antes de inserirmos na estrutura: se false-> insere; senao nao insere.
 */
 //-----------------------------------------------------------------------------


//noh da estrutura
//contem um ponteiro para o proximo elemento e o dado que é armazenado
template<class tipoData>
struct strNodeLinkedList
{
    strNodeLinkedList *next; //ponteiro para a proxima estrutura (kdNodeData)
    tipoData data;

};



template<class tipoData>
class DTALinkedList
{
      public:
        DTALinkedList();
        ~DTALinkedList();
        strNodeLinkedList<tipoData>* addData(tipoData dt);
        bool removeData(tipoData dt);
        bool findData(tipoData dt);
        strNodeLinkedList<tipoData>* findPointer(tipoData dt);
        void printDataFolha();
        int getNumReg();
        void removeAll();
        const tipoData* operator [] (int i);
        const tipoData* getData(int posicao);
        vector<tipoData>* getAllData();

    private:
        int numReg; //numero de registros armazenados
        strNodeLinkedList<tipoData> *cabeca; //cabeca da lista encadeada
};

template<class tipoData>
DTALinkedList<tipoData>::DTALinkedList()
{
    cabeca = new strNodeLinkedList<tipoData>;
    cabeca->next = NULL;
    numReg =0;
};

template<class tipoData>
DTALinkedList<tipoData>::~DTALinkedList()
{

    strNodeLinkedList<tipoData> *ptr, *aux;
    ptr = cabeca->next;

    while( ptr != NULL)
    {
        aux = ptr;
        ptr = ptr->next;
        delete(aux);
    }

    delete cabeca;
};

template<class tipoData>
strNodeLinkedList<tipoData>* DTALinkedList<tipoData>::addData(tipoData dt)
{
    strNodeLinkedList<tipoData> *newElement; //novo elemento a ser inserido na estrutura
    strNodeLinkedList<tipoData> *back; //elemento imediatamente anteior ao ponteiro de insercao
    strNodeLinkedList<tipoData> *trace; //ponteiro para percorrer os elementos

    if(cabeca->next == NULL) //ainda nao temos nenhum elemento armazenado
    {
      //  cout << "cabeca->next: NULL"<< endl;
        newElement = new strNodeLinkedList<tipoData>;
        newElement->data = dt;
        newElement->next = NULL;
        cabeca->next = newElement;
    }
    else //buscamos a posicao correta de insercao
    {
      //  cout << "cabeca->next nao NULL" << endl;
        trace = cabeca->next;
        back = cabeca;
        while( trace !=NULL && dt >= trace->data )
        {
            //cout << "entrou no while" << endl;
            back = trace;
            trace =  trace->next;
        }

        if( trace == NULL ) //percorreu todos os elementos e chegou no final
        {
           // cout << "trace eh null" << endl;
            newElement = new strNodeLinkedList<tipoData>; //cria um novo n�
            newElement->data = dt;
            newElement->next = NULL;

            back->next = newElement;//faz o elemento anteior a trace apontar para o novo elemento
        }
        else //o elemento deve ser inserido na ordem
        {
            strNodeLinkedList<tipoData> *ptrAux; //armazena onde o elemento atual esta apontando
            newElement = new strNodeLinkedList<tipoData>; //cria um novo n�
            newElement->data = dt;

            back->next = newElement;
            newElement->next = trace;
        }
    }
    numReg++;
    return newElement;
};

template<class tipoData>
void DTALinkedList<tipoData>::printDataFolha()
{
    strNodeLinkedList<tipoData> *ptr;
    ptr = cabeca->next;
    while( ptr != NULL)
    {
     cout << ptr->data << " ";
     ptr = ptr->next;
    }
    cout << endl;
}

template<class tipoData>
bool DTALinkedList<tipoData>::removeData(tipoData dt)
{
    strNodeLinkedList<tipoData> *ptr; //ponteiro para percorrer a estrutura
    strNodeLinkedList<tipoData> *back; //ponteiro anterior aa ptr
    strNodeLinkedList<tipoData> *aux; //ponteiro anterior que recebe o elemento que sera removido, para deletarmos depois

    ptr = cabeca->next;
    back = cabeca;

    while(ptr != NULL && ptr->data != dt)
    {
        back = ptr;
        ptr = ptr->next;
    }

    if( ptr != NULL)
    {
        aux = ptr;
        back->next = ptr->next;
        delete aux;
        numReg--;
        return true;

    }

    return false;
};


template<class tipoData>
bool DTALinkedList<tipoData>::findData(tipoData dt)
{
    
    strNodeLinkedList<tipoData> *ptr; //ponteiro para percorrer a estrutura
    ptr= cabeca->next;    
    bool achou = false;
    
    while( ptr != NULL && achou == false)
    {

        if( dt == ptr->data )
            achou = true;
        else
          //  if( dt < ptr->data )
          //      ptr= NULL;
          // else
                ptr=ptr->next;
          
          
    }

     return achou;

};


template<class tipoData>
int DTALinkedList<tipoData>::getNumReg()
{
    return numReg;
};

template<class tipoData>
void DTALinkedList<tipoData>::removeAll()
{
   strNodeLinkedList<tipoData> *ptr, *aux;
    ptr = cabeca->next;

    while( ptr != NULL)
    {
        aux = ptr;
        ptr = ptr->next;
        delete(aux);
    }

    cabeca->next = NULL;
    numReg = 0;


};

template<class tipoData>
strNodeLinkedList<tipoData>* DTALinkedList<tipoData>::findPointer(tipoData dt)
{

    strNodeLinkedList<tipoData> *ptr; //ponteiro para percorrer a estrutura
    strNodeLinkedList<tipoData> *ret;

    ptr= cabeca->next;
    bool achou = false;
    ret = NULL;

    while( ptr != NULL && achou == false)
    {

        if( dt == ptr->data )
        {
            achou = true;
            ret  = ptr;
        }
        else
       //     if( dt < ptr->data )
       //         ptr= NULL;
       //     else
                ptr=ptr->next;


    }

     return ret;
}


template<class tipoData>
const tipoData* DTALinkedList<tipoData>::getData(int posicao)
{
    register int j;
    const tipoData* ret;
    ret = NULL;
    strNodeLinkedList<tipoData> *ptr;
    ptr = cabeca->next; //vai ao ponteiro onde os dados comecam a ser colocados

   // cout <<"Valor de i em DTALinkedList" <<posicao<< endl;
    //isso trata o caso onde i==0
    if( posicao>=0)
    {
    if(ptr != NULL)
        ret = &ptr->data;

    j=0;
    while(ptr!=NULL && j<=posicao )
    {
        ret = &ptr->data;
        ptr = ptr->next;
        j++;
    }

    if(j<=posicao)
        ret = NULL;
    }

    return ret;
}

template<class tipoData>
const tipoData* DTALinkedList<tipoData>::operator [](int i)
{
    register int j;
    const tipoData* ret;
    ret = NULL;
    strNodeLinkedList<tipoData> *ptr;
    ptr = cabeca->next; //vai ao ponteiro onde os dados comecam a ser colocados

   // cout <<"Valor de i em DTALinkedList" <<i<< endl;
    //isso trata o caso onde i==0
    if( i>=0)
    {
    if(ptr != NULL)
        ret = &ptr->data;

    j=0;
    while(ptr!=NULL && j<=i )
    {
        ret = &ptr->data;
        ptr = ptr->next;
        j++;
    }

    if(j<=i)
        ret = NULL;
    }

    return ret;
}

template<class tipoData>
vector<tipoData>* DTALinkedList<tipoData>::getAllData()
{
    vector<tipoData> *saida = new vector<tipoData>;
    strNodeLinkedList<tipoData> *ptr;
    ptr = cabeca->next; //vai ao ponteiro onde os dados comecam a ser colocados

    while( ptr!=NULL)
    {
        saida->push_back(ptr->data);
        ptr = ptr->next;
    }

    return saida;
}

#endif // DTALINKEDLIST_H_INCLUDED
